package Lee_code;

import java.util.ArrayList;
import java.util.List;

/**
 * @author blh
 * @date 2024年09月17日 15:35
 */

public class Lee_207_917 {
    List<List<Integer>> edges = new ArrayList<>();
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int num = prerequisites.length;
        for (int i = 0; i < num; i++) {
            edges.add(new ArrayList<>());
        }
        visited = new int[num];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    /**
     * 0-未遍历
     * 1-正在遍历
     * 2-已经遍历完毕
     */
    private void dfs(int u) {
        visited[u] = 1;
        for (Integer v : edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
                // 遍历到了正在遍历的节点->出现了环
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}
